#include <iostream>
#include <Windows.h>

using namespace std;

/* Problem description:
 * A robot is located at the top-left corner of a m x n grid. 
 * The robot can only move either down or right at any point in time. 
 * The robot is trying to reach the bottom-right corner of the grid. 
 * How many possible unique paths are there?
 * 
 * This is from the following link: http://www.leetcode.com/2010/11/unique-paths.html
 * The interesting thing is: the DP is not the best solution always, as to init DPTable 
 * and update it also introduces more over head. If the 
 */

/*
 * Follow up question, what if to print all paths? 
 * Using the backtracking, see the following solution. 
 */

int COL = 15;
int ROW = 15;

int DpTable[17][17];

/* Algorithm:
 * 
 * The total unique paths at grid (r,c) is equal to the sum of total unique paths 
 * from grid to the right (r,c+1) and the grid below (r+1,c).
 */ 

//
// This is regular recursive function
//
int GetUniquePath1(int col, int row)
{
    if (col == 1 || row == 1)
        return 1;

    return GetUniquePath1(col-1, row) + GetUniquePath1(col, row-1);
}

void InitDpTable()
{
	for(int i=0; i<=ROW; i++ )
	{
		for(int j=0; j<=COL; j++)
		{
			DpTable[i][j]=0;
		}
	}
}

//
// This algorithm allocate a DP table and make sure each
// bucket is calculated once. but it still use the system stacks
//
int GetUniquePath2(int row, int col)
{
	if( row>ROW || col>COL)
		return -1;

    if (col == 1 || row == 1)
        return 1;
	
	if( DpTable[row-1][col] == 0 )
	{
		DpTable[row-1][col] = GetUniquePath2(row-1, col);
	}

	if( DpTable[row][col-1] == 0 )
	{
		DpTable[row][col-1] = GetUniquePath2(row, col-1 );
	}
	
    return DpTable[row-1][col] + DpTable[row][col-1];
}

//
// NON-recursive DP solution
// O(row*col)
//
int GetUniquePath3(int row, int col)
{
	InitDpTable();
	DpTable[0][1] = 1;

	if( row>ROW || col>COL)
		return -1;

	for( int i=1; i<=row; i++ )
	{
		for( int j=1; j<=col;j++ )
		{
			DpTable[i][j] = DpTable[i-1][j]+DpTable[i][j-1];
		}
	}
    
    return DpTable[row][col];
}

const int OffsetCount = 2;
int RowOffset[OffsetCount]={0,1};
int ColOffset[OffsetCount]={1,0};

bool IsSafe( int col, int row )
{
	return ((col<=COL&&row<=ROW)?true:false); 
}

void PrintTable()
{
	for( int i=1; i<=ROW;i++)
	{
		for( int j=1; j<=COL;j++)
		{
			cout<<DpTable[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
}

// it can be simplified to use a array instead of a table
void PrintAllPath(int col, int row, int &sum)
{
	if( col == COL && row == ROW )
	{
		sum++;
		//PrintTable();
		return;
	}

	for( int i=0; i<OffsetCount; i++ )
	{
		if( IsSafe(col+ColOffset[i], row+RowOffset[i]) )
		{
			DpTable[col+ColOffset[i]][row+RowOffset[i]] = 1;
			PrintAllPath( col+ColOffset[i], row+RowOffset[i], sum);
			DpTable[col+ColOffset[i]][row+RowOffset[i]] = 0;
		}
	}
}


void Test()
{
    int col=COL, row=ROW;
    int numPath = 0;
	FILETIME startTime;
	FILETIME endTime;
	
	GetSystemTimes(NULL, NULL, &startTime);
	numPath = GetUniquePath1(col, row);
	GetSystemTimes(NULL, NULL, &endTime);
    cout<< "Number of unique path (algorithm 1) of [" << col << "," << row << "] is: " << numPath << endl;
	cout<<"Consumed Time "<<endTime.dwLowDateTime-startTime.dwLowDateTime<<" ticks"<<endl;

	startTime = endTime;
	InitDpTable();
	numPath = GetUniquePath2(row, col);
	GetSystemTimes(NULL, NULL, &endTime);
    cout<< "Number of unique path (algorithm 2) of [" << col << "," << row << "] is: " << numPath << endl;
	cout<<"Consumed Time "<<endTime.dwLowDateTime-startTime.dwLowDateTime<<" ticks"<<endl;

	startTime = endTime;
 	numPath = GetUniquePath3(row, col);
	GetSystemTimes(NULL, NULL, &endTime);
    cout<< "Number of unique path (algorithm 3) of [" << col << "," << row << "] is: " << numPath << endl;
 	cout<<"Consumed Time "<<endTime.dwLowDateTime-startTime.dwLowDateTime<<" ticks"<<endl;

	startTime = endTime;
	numPath = 0;
	InitDpTable();
	DpTable[1][1] = 1;
	PrintAllPath(1, 1, numPath);
	GetSystemTimes(NULL, NULL, &endTime);
    cout<< "Number of unique path enumeration of [" << col << "," << row << "] is: " << numPath << endl;
	cout<<"Consumed Time "<<endTime.dwLowDateTime-startTime.dwLowDateTime<<" ticks"<<endl;
}

int main()
{
	for( int i=5; i<=15; i++ )
	{
		COL = ROW = i;
		Test();
		cout<<endl;
	}
	
	cout << "Press any key to exit... " << endl;

    return getchar();
}

